package jannex.label;

import jannex.internal.Hashing;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;

/**
 * Cannot contain null Equals uses equalsIgnoreCase
 */
public abstract class LabelSet extends AbstractSet<String> {

    private static final LabelSet EMPTY = new EmptyLabelSet();

    public static LabelSet of(String... labels) {
        return construct(labels);
    }

    public static LabelSet empty() {
        return EMPTY;
    }

    public static Builder builder(int initialSize) {
        return new Builder(initialSize);
    }

    public static Builder builder() {
        return new Builder(4);
    }

    @Override
    @Deprecated
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    @Deprecated
    public boolean add(String label) {
        throw new UnsupportedOperationException();
    }

    @Override
    @Deprecated
    public boolean addAll(Collection<? extends String> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    @Deprecated
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    @Deprecated
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    @Deprecated
    public void clear() {
        throw new UnsupportedOperationException();
    }

    public abstract LabelList asList();

    @Override
    public abstract String[] toArray();

    public static class Builder {

        private ArrayList<String> list;

        Builder(int initialSize) {
            this.list = new ArrayList<>(initialSize);
        }

        public Builder add(String label) {
            if (label == null) {
                throw new NullPointerException();
            }
            list.add(label);
            return this;
        }

        public Builder addAll(Iterable<String> labels) {
            for (String label : labels) {
                add(label);
            }
            return this;
        }

        public final Builder addAll(String... labels) {
            return addAll(Arrays.asList(labels));
        }

        public LabelSet build() {
            return construct(list.toArray(new String[list.size()]));
        }

    }

    // We use power-of-2 tables, and this is the highest int that's a power of 2
    static final int MAX_TABLE_SIZE = 1 << (Integer.SIZE - 2);

    // If the set has this many elements, it will "max out" the table size
    static final int CUTOFF = (int) Math.floor(MAX_TABLE_SIZE * 0.7);

    static int chooseTableSize(int setSize) {
        if (setSize < CUTOFF) {
            int tableSize = Integer.highestOneBit(setSize - 1) << 1;
            while (tableSize * 0.7 < setSize) {
                tableSize <<= 1;
            }
            return tableSize;
        }
        return MAX_TABLE_SIZE;
    }

    private static LabelSet construct(String... labels) {
        if (labels.length == 0) {
            return EMPTY;
        } else if (labels.length == 1) {
            return new SingletonLabelSet(labels[0]);
        }
        int tableSize = chooseTableSize(labels.length);
        String[] table = new String[tableSize];
        ArrayList<String> uniqueElementsList = null;
        for (int i = 0; i < labels.length; i++) {
            String label = labels[i];
            int hash = label.toLowerCase().hashCode();
            for (int j = Hashing.smear(hash); ; j++) {
                int index = j & (tableSize-1);
                String oldLabel = table[index];
                if (oldLabel == null) {
                    if (uniqueElementsList != null) {
                        uniqueElementsList.add(label);
                    }
                    // Came to an empty slot. Put the label here.
                    table[index] = label;
                    break;
                } else if (oldLabel.equalsIgnoreCase(label)) {
                    if (uniqueElementsList == null) {
                        // first dup
                        uniqueElementsList = new ArrayList<>(labels.length);
                        for (int k = 0; k < i; k++) {
                            String previous = labels[k];
                            uniqueElementsList.add(previous);
                        }
                    }
                    break;
                }
            }
        }
        String[] uniqueElements = uniqueElementsList == null
                ? labels
                : uniqueElementsList.toArray(new String[uniqueElementsList.size()]);
        if (uniqueElements.length == 1) {
            String element = uniqueElements[0];
            return new SingletonLabelSet(element);
        } else if (tableSize != chooseTableSize(uniqueElements.length)) {
            // Resize the table when the array includes too many duplicates.
            // when this happens, we have already made a copy
            return construct(uniqueElements);
        } else {
            return new ArrayLabelSet(uniqueElements, table);
        }
    }
}
